//
//
//class Solution {
//
//    Map<Character, List<Character>> hash = new HashMap<>();
//    List<String> ret = new ArrayList<>();
//    StringBuilder cur = new StringBuilder();
//
//    public List<String> letterCombinations(String digits) {
//        if (digits == null || digits.length() == 0) return ret;
//        init(hash);
//        dfs(digits.toCharArray(), 0);
//        return ret;
//    }
//
//
//    public void dfs(char[] arr, int index) {
//        if (cur.length() == arr.length) {
//            ret.add(new StringBuilder(cur).toString());
//        }
//        if (index < 0 || index >= arr.length) return;
//        char ch = arr[index];
//        List<Character> list = hash.getOrDefault(ch, new ArrayList<>());
//        for (int i = 0; i < list.size(); i++) {
//            cur.append(list.get(i));
//            dfs(arr, index + 1);
//            cur.deleteCharAt(cur.length() - 1);
//        }
//    }
//
//    public void init(Map<Character, List<Character>> hash) {
//        char ch = 'a';
//        for (int i = 2; i <= 9; i++) {
//            List<Character> tmp = new ArrayList<>();
//            for (int j = 0; j < 3; j++) {
//                tmp.add(ch);
//                ch++;
//            }
//            if (i == 7 || i == 9) {
//                tmp.add(ch);
//                ch++;
//            }
//            hash.put((char) (i + '0'), tmp);
//        }
//    }
//}